package edu.cmu.cs211.compression.tests;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Set;
import java.util.Vector;

import org.junit.Test;

import edu.cmu.cs211.compression.util.MyPriorityQueue;

/*
 * Some of the provided tests were left for you to finish implementing.
 */
public class PriorityQueueTest
{
  /** A simple test that offers one element into the pq */
  @Test
  public void testOffer()
  {
	  /* test MypriorityQueue built out of a collection */
	  Vector<Integer> intVector = new Vector<Integer>();
	  
	  for(int i = 31; i >0; i-=2)
	  	intVector.add(i);

	   MyPriorityQueue<Integer> testCollection = new MyPriorityQueue<Integer>(intVector);
	   
	   assertEquals("1st min in testCollection", new Integer(1), testCollection.poll());
	   assertEquals("2nd min in testCollection", new Integer(3), testCollection.poll());
	   
	   
	   /* test inserting into a string pq */
	   MyPriorityQueue<String> pq = new MyPriorityQueue<String>();

	   boolean ret = pq.offer("blah");
	   assertEquals("offer on queue returns true", true, ret);
	   assertEquals("size on queue returns 1 after insert", 1, pq.size());

	   
	   /* test inserting integer into pq */
	   MyPriorityQueue<Integer> testInt = new MyPriorityQueue<Integer>();
	   for(int i = 0; i < 20; i += 2)
		   testInt.offer(i);
    
	   assertEquals("peek 1st min in testInt", new Integer(0), testInt.peek());
	   assertEquals("poll 1st min in testInt", new Integer(0), testInt.poll());
	   
	   
	   /* test custome object */
	   class Node
	   {
		   public int i;
		   public Node(int j)
		   {
			   this.i = j;
		   }
	   }
	   
	   Comparator<Node> c = new Comparator<Node>()
	   {
		   @Override
		   public int compare(Node arg0, Node arg1) {
			   return arg0.i - arg1.i;
		   };
	   };
	   
	   MyPriorityQueue<Node> nodeq = new MyPriorityQueue<Node>(c);
	   for(int i = 1; i < 25; i+=3)
		   nodeq.offer(new Node(i));
	   
	   assertEquals("1st min in nodeq", 1, nodeq.poll().i);
	   assertEquals("2nd min in nodeq", 4, nodeq.poll().i);
	   assertEquals("size of nodeq after polling twice", 6, nodeq.size());
	   
	   
	   /* test a customized backwards comparator */
	   Comparator<Integer> backwards = new Comparator<Integer>()
	   {
		   @Override
		   public int compare(Integer arg0, Integer arg1) {
			   return arg1-arg0;
			   };
	   };
	   
	   MyPriorityQueue<Integer> testBackwards = new MyPriorityQueue<Integer>(backwards);
	   for(int i = 0; i < 20; i += 2)
		   testBackwards.offer(i);
	   
	   assertEquals("1st min in testBackwards", new Integer(18), testBackwards.poll());
	   assertEquals("2nd min in testBackwards", new Integer(16), testBackwards.poll());
  }

  /** PQ does not allow a negative initial capacity */
  @Test(expected = IllegalArgumentException.class)
  public void capacityIllegalNeg()
  {
    new MyPriorityQueue<Object>(-2);
  }

  @Test (expected = NullPointerException.class)
  public void nullTest()
  {
    //TODO: what should the behavior of the priority queue be
    // for null objects?
	  MyPriorityQueue<Integer> nullqueue = new MyPriorityQueue<Integer>();
	  nullqueue.offer(null);
  }
  
  @Test
  public void stressTest()
  {
    PriorityQueue<Integer>   java = new PriorityQueue<Integer>();
    MyPriorityQueue<Integer> mine = new MyPriorityQueue<Integer>();
    
    Random r      = new Random();
    int    NITERS = 10000;

    for( int i = 0; i < NITERS; ++i )
    {
      //Create an element to potentially add to the PQ
      Integer mightadd = Integer.valueOf(r.nextInt(100));
      
      //TODO: randomly select an operation that mutates the queue
      // we want to be sure that the queue grows, so we add with
      // higher probability than removing
      if( r.nextFloat() < 0.66f )
      {
    	  java.offer(mightadd);
    	  mine.offer(mightadd);
      }
      else
      {
    	  java.poll();
          mine.poll();
      }
      
      //Make sure the state is still consistent
      assertPQequal(mine, java);
    }
  }
  
  /**
   * It is often helpful when you are unit testing a data strcture
   * to write helper methods that make sure that the state of your
   * data structure are consistent at any given point in time.
   * 
   * This method takes two priority queues and compares them for equality.
   */
  private <E> void assertPQequal(MyPriorityQueue<E> actual, PriorityQueue<E> expected)
  {
    //TODO: What else could we test here without modifying the PQ?
    

    //Array list uses the iterator of PQ to get all the elements
    // so this tests that your iterator returns all of the elements
    // in the PQ
    List<E> actual_elems = new ArrayList<E>(actual);
    List<E> expected_elems = new ArrayList<E>(expected);
    
    //Because the order of elements returned by the iterator is unspecified,
    //we restore a canonical ordering for the elements by sorting them.
    Collections.sort(actual_elems, actual.comparator());
    Collections.sort(expected_elems, expected.comparator());

    assertEquals(actual_elems, expected_elems);
  }
}
